package Demo;

// 定义线性表的类
class LinearList {
    Node head; // 线性表的头节点
    int size; // 线性表的长度

    // 构造方法，初始化线性表为空表
    public LinearList() {
        head = null;
        size = 0;
    }

    // 判断线性表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在线性表的末尾添加一个元素
    public void add(char c) {
        // 如果元素已经存在于线性表中，不做任何操作
        if (contains(c)) {
            return;
        }
        // 创建一个新的节点，数据为c，后继指针为null
        Node newNode = new Node(c, null);
        // 如果线性表为空，将新节点作为头节点
        if (isEmpty()) {
            head = newNode;
        } else {
            // 否则，找到线性表的最后一个节点，将其后继指针指向新节点
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
        // 线性表长度加一
        size++;
    }

    // 判断线性表是否包含某个元素
    public boolean contains(char c) {
        // 从头节点开始遍历线性表，比较每个节点的数据是否等于c
        Node current = head;
        while (current != null) {
            if (current.data == c) {
                return true; // 如果找到相等的数据，返回true
            }
            current = current.next; // 否则，继续遍历下一个节点
        }
        return false; // 如果遍历完毕没有找到相等的数据，返回false
    }

    // 返回线性表的长度
    public int size() {
        return size;
    }

    // 返回线性表的字符串表示，用方括号括起来，元素之间用逗号分隔
    public String toString() {
        StringBuilder sb = new StringBuilder(); // 创建一个字符串构建器
        sb.append("["); // 添加左方括号
        Node current = head; // 从头节点开始遍历线性表
        while (current != null) {
            sb.append(current.data); // 将每个节点的数据添加到字符串构建器中
            if (current.next != null) {
                sb.append(", "); // 如果不是最后一个节点，添加逗号和空格
            }
            current = current.next; // 继续遍历下一个节点
        }
        sb.append("]"); // 添加右方括号
        return sb.toString(); // 返回字符串构建器的内容
    }

    // 返回两个线性表的并集，即包含两个线性表中所有不重复的元素的新线性表
    public static LinearList union(LinearList list1, LinearList list2) {
        LinearList result = new LinearList(); // 创建一个新的空线性表作为结果
        Node current1 = list1.head; // 从list1的头节点开始遍历
        while (current1 != null) {
            result.add(current1.data); // 将list1中的每个元素添加到结果中（如果不存在）
            current1 = current1.next; // 继续遍历下一个节点
        }
        Node current2 = list2.head; // 从list2的头节点开始遍历
        while (current2 != null) {
            result.add(current2.data); // 将list2中的每个元素添加到结果中（如果不存在）
            current2 = current2.next; // 继续遍历下一个节点
        }
        return result; // 返回结果
    }

    // 返回两个线性表的交集，即包含两个线性表中共有的元素的新线性表
    public static LinearList intersection(LinearList list1, LinearList list2) {
        LinearList result = new LinearList(); // 创建一个新的空线性表作为结果
        Node current1 = list1.head; // 从list1的头节点开始遍历
        while (current1 != null) {
            // 如果list1中的元素也存在于list2中，将其添加到结果中（如果不存在）
            if (list2.contains(current1.data)) {
                result.add(current1.data);
            }
            current1 = current1.next; // 继续遍历下一个节点
        }
        return result; // 返回结果
    }

    // 返回两个线性表的差集，即包含list1中存在而list2中不存在的元素的新线性表
    public static LinearList difference(LinearList list1, LinearList list2) {
        LinearList result = new LinearList(); // 创建一个新的空线性表作为结果
        Node current1 = list1.head; // 从list1的头节点开始遍历
        while (current1 != null) {
            // 如果list1中的元素不存在于list2中，将其添加到结果中（如果不存在）
            if (!list2.contains(current1.data)) {
                result.add(current1.data);
            }
            current1 = current1.next; // 继续遍历下一个节点
        }
        return result; // 返回结果
    }
}